|
Chris Pollett > Old
Classes > |
CS154 Spring 2007Practice FinalTo study for the final would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice midterm is below. Here are some facts about the actual final: (a) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (b) You should bring photo ID. (c) There will be more than one version of the test. Each version will be of comparable difficulty. (d) It is comprehensive: There will be two problems from the material up to Midterm 1 (one of these will be from Practice Midterm 1); there will be two problems from the material up to Midterm 2 (one of these will be from Practice Midterm 2); the reamining six problems will be on material since Midterm 2 (one of these will be from the Practice Final). [Student Generated Solutions-PDF] 1. Prove that the language {<M,x> | M halts on input x } is undecidable 2. Prove that the problem of determining whether a CFG generates all strings over some alphabet is undecidable. 3. Show directly that a k-tape nondeterministic Turing machine can be simulated by a 1-tape nondeterministic Turing machine 4. In class we argued that a for any nondeterministic Turing machine which computes a language in time f(n) there is a constant c such that it can be simulated by a deterministic machine running in time cf(n). How is c determined? 5. Give a Turing reduction from the problem the halting problem to the problem of determining whether a Turing machine has a useless state (that is, a state that is not used in any computation). 6. In class, we said that an offline Turing machine is usually used to measure the space complexity of algorithms. Why is this model used over usual Turing machines? 7. Prove that every decidable language is Turing reducible to a regular language. Give an example of an r.e. language which is not reducible to a regular language 8. Give the diagram for a Turing machine which reverses whatever string is initially on its tape. 9. Consider the language { <M,x, n> | M on input x halts in fewer than n steps}. Is this language decidable? Why or why not? 10. Show that there is a language which is r.e. but not co-r.e. |